/**
 * 以下四种情况可能产生违反AVL树性质：
 * 1. 在结点X的左孩子结点的左子树上插入元素
 * 2. 在结点X的左孩子结点的右子树上插入元素
 * 3. 在结点X的右孩子结点的左子树上插入元素
 * 4. 在结点X的右孩子结点的右子树上插入元素
*/
typedef struct TreeNode
{
    int height;
    TreeNode *left;
    TreeNode *right;
    const char *data;
} TreeNode;

class AVLTree
{
private:
    TreeNode *root;
    TreeNode *singleRotateLeft(TreeNode *node);
    TreeNode *singleRotateRight(TreeNode *node);
    TreeNode *doubleRotateLeft(TreeNode *node);
    TreeNode *doubleRotateRight(TreeNode *node);
    int height(TreeNode *node);
    int maxHeight(TreeNode *n1, TreeNode *n2);
    TreeNode *insert(TreeNode *parent, TreeNode *newNode);
    int isAVL(TreeNode *node);
    TreeNode *removeHalfNodes(TreeNode *node);
    TreeNode *removeLeaves(TreeNode *node);
    TreeNode *pruneBST(TreeNode *node, const char *mindata, const char *maxdata);

public:
    AVLTree(const char *data);
    TreeNode *insert(const char *data);
    int isAVL();
    TreeNode *removeHalfNodes();
    TreeNode *removeLeaves();
    TreeNode *pruneBST(const char *mindata, const char *maxdata);
};